package random;

import java.util.HashMap;
import java.util.Map;

/**
 * 和相同的二元子数组
 *
 * 给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。
 * 子数组 是数组的一段连续部分。
 */

public class L930 {

    public static void main(String[] args) {
        System.out.println(new L930().numSubarraysWithSum(new int[]{0,0,0,0,0}, 0));
    }

    /**
     * 暴力捞捞解法， n^2复杂度
     * @param nums
     * @param goal
     * @return
     */
    public int numSubarraysWithSum(int[] nums, int goal) {

        int count = 0;
        for (int i = 0; i < nums.length; i++) {

            int sum = 0;
            sum = nums[i];
            if (sum == goal) count++;
            for (int j = i+1; j < nums.length; j++) {
                sum += nums[j];
                if (sum == goal) {
                    count++;
                }else if (sum > goal){
                    break;
                }
            }
        }
        return count;
    }


    /**
     * 哈希表解法
     * @param nums
     * @param goal
     * @return
     */
    public int numSubarraysWithSum1(int[] nums, int goal) {
        int sum = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        int ret = 0;    // 统计
        for (int num : nums) {
            cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);     // 记录每一种前缀和出现的次数
            sum += num;
            ret += cnt.getOrDefault(sum - goal, 0);     // 只需要查询哈希表中元素 sum[j]−goal 的数量即可
        }
        return ret;
    }

/*    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/binary-subarrays-with-sum/solution/he-xiang-tong-de-er-yuan-zi-shu-zu-by-le-5caf/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/


    /**
     * 滑动窗口 其实就是右边边界控制，然后左边两个边界用来统计，left1边界用来判断最大可圈的范围，left2边界用来判断里面可以圈的范围，因为如果有零的话范围是可以再圈的
     */
    public int numSubarraysWithSum2(int[] nums, int goal) {
        int n = nums.length;
        int left1 = 0, left2 = 0, right = 0;
        int sum1 = 0, sum2 = 0;
        int ret = 0;
        while (right < n) {
            sum1 += nums[right];
            while (left1 <= right && sum1 > goal) {     // 如果和 大于goal，则先减去 再加一
                sum1 -= nums[left1];
                left1++;
            }
            sum2 += nums[right];
            while (left2 <= right && sum2 >= goal) {    // 如果和 大于等于goal，则先减去 再加一
                sum2 -= nums[left2];
                left2++;
            }
            ret += left2 - left1;
            right++;
        }
        return ret;
    }

   /* 作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/binary-subarrays-with-sum/solution/he-xiang-tong-de-er-yuan-zi-shu-zu-by-le-5caf/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
}
